// 2025/2/27
// https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=problem-list-v2&envId=binary-search
// 搜索旋转数组

class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            int left = 1, right = n - 1;
            int mid = (left + right) / 2;
            while (left <= right) {
                mid = (left + right) / 2;
    
                if (nums[mid] > nums[0])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
    
            if(mid < n - 1 && nums[mid] > nums[mid + 1])
                ++mid;
    
            if(nums[0] < nums[n - 1])
            {
                left = 0;
                right = n - 1;
            }
            else if (target >= nums[0]) {
                left = 0;
                right = max(mid - 1, 0);
            } else {
                left = mid;
                right = n - 1;
            }
    
            while (left <= right) {
                mid = (left + right) / 2;
    
                if (nums[mid] > target)
                    right = mid - 1;
                else if (nums[mid] < target)
                    left = mid + 1;
                else
                    return mid;
            }
            return -1;
        }
    };